import unittest
from z3 import *


class DynamicProgramming(unittest.TestCase):
    def test_dp(self):
        pass

    def test_fibonacci_dp(self):
        n = 9
        if n <= 1:
            return n
        # 定义一个n+1长度数组
        dp = [0] * (n + 1)
        dp[0], dp[1] = 0, 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        print(dp[n])

    def test_fibonacci_recursion(self):
        n = 9

        def fii(n):
            print(f'calc {n}')
            if n <= 1:
                return n
            else:
                return fii(n - 1) + fii(n - 2)

        print(fii(n))
